package chapter01;

public class RemoveNthFromEnd {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    //添加一个哑结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int sum=0,i=0;
        ListNode p=head,pre=new ListNode(0,head);
        ListNode preHead=pre;
        sum=getLength(head);
        while(p!=null){
            i++;
            if(i==sum-n+1){
                pre.next=p.next;
            }
            pre=p;
            p=p.next;
        }
        return preHead.next;
    }

    public int getLength(ListNode head){
        int sum=0;
        ListNode p=head;
        while(p!=null){
            sum++;
            p=p.next;
        }
        return sum;
    }
}
